#pragma once

#include "CommonToAll.hpp"
#include "ObjectPool.hpp"

using std::cout;
using std::endl;
using std::vector;

class SizeClass
{
public:
    static size_t RoundUp(size_t size) // 计算对齐字节数
    {
        if (size <= 128)
        {
            // 8B
            return _RoundUp(size, 8);
        }
        else if (size <= 1024)
        {
            // 16B
            return _RoundUp(size, 16);
        }
        else if (size <= 8 * 1024)
        {
            // 128B
            return _RoundUp(size, 128);
        }
        else if (size <= 64 * 1024)
        {
            // 1024B
            return _RoundUp(size, 1024);
        }
        else if (size <= 256 * 1024)
        {
            // 8*1024B
            return _RoundUp(size, 8 * 1024);
        }
        else // 不可能，已经超出了最大字节数
        {
            return _RoundUp(size, 1 << PAGE_SHIFT); // 已经超过了最多的256kb，此时就按页进行对齐
            // assert(false);
            // return -1;
        }
    }
    // 写法一：以十进制为基准进行计算
    //  static size_t _RoundUp(size_t size, size_t align_num)//用于计算每个分区后的字节数
    //  {
    //      size_t res = 0;
    //      if(size % align_num)
    //          //eg：size为3，(3/8+1)*8 = 8，对齐后的字节数为8
    //          res = (size / align_num + 1) * align_num;
    //      else res = size;//说明其本身就能作为对齐后的字节数

    //     return res;
    // }
    // 写法二：以二进制位基准进行计算
    static size_t _RoundUp(size_t size, size_t align_num)
    {
        return (size + align_num - 1) & ~(align_num - 1);
    }

public:
    static inline size_t Index(size_t size) // 与哈希桶形成映射关系，返回哈希桶的位置
    {
        assert(size <= MAX_BYTES);

        static int group_array[4] = {16, 56, 56, 56};
        if (size <= 128)
        {
            return _Index(size, 3);
        }
        else if (size <= 1024)
        {
            return _Index(size - 128, 4) + group_array[0];
        }
        else if (size <= 8 * 1024)
        {
            return _Index(size - 1024, 7) + group_array[1] + group_array[0];
        }
        else if (size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
        }
        else if (size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
        }
        else
        {
            assert(false);
        }
        return -1;
    }
    static inline size_t _Index(size_t size, size_t alig_shift /*对齐数的二进制位数*/) // 计算size对应的哈希桶的下标
    {
        // 1 << alig_shift：这一步是通过对齐数的二进制位数还原原本的对齐数
        // size + alignNum - 1：这一步是进行向上取整
        // (size + alignNum - 1) >> alig_shift：这一步是在除以对齐数
        // 最后的 -1：是由于数组下标是从0开始的，所以需要我们进行-1
        return ((size + (1 << alig_shift) - 1) >> alig_shift) - 1;
    }
    static size_t NumMoveSize(size_t size) // 能够申请块的最大数量
    {
        assert(size); // 申请的size大小不能为0

        size_t num = MAX_BYTES / size; // MAX_BYTES就是256kb

        if (num > 512)
        {
            /*当这里的size为8b的时候，
            num超过了512块，
            假如直接根据上面的num给对应的块的话，
            会造成很大的空间浪费*/
            num = 512;
        }

        if (num < 2)
        {
            /*当这里的size为256kb的时候，num为1
            上限就是为1，但是假如线程需要的是4*256kb
            num设置为2，这样就可以少调度几次，减小开销
            但是也不能给太多，假如将num设置为4，
            那浪费的空间可能会比较大*/
            num = 2;
        }

        //[2,512]一次批量移动多少个内存块给对象的上限值(慢启动)
        // 小对象上限高
        // 大对象上限低

        return num;
    }
    static size_t NumMovePage(size_t size /*根据申请的size来计算所需要的页的数量*/) // 申请页的数量
    {
        size_t num = NumMoveSize(size); // 计算出该size下对应的块的数量

        size_t npage = num * size; // npage就是指的当前单次申请的空间的大小

        npage >>= PAGE_SHIFT; // 右移操作相当于除法，除以一张页的大小得到的就是当前所需要的页的数量

        if (npage == 0) // 分配页给CentralCache至少要分配一页空间
            npage = 1;
        return npage;
    }
};

static                 /*ObjNext用static修饰，防止多个.cpp文件重复包含该Common头文件导致链接时产生冲突*/
    void *&            /*这里需要引用，因为后面要对这个返回值进行处理，不使用引用就会造成返回值是一个右值，无法被修改*/
    ObjNext(void *obj) // obj的头4/8个字节
{
    return *(void **)obj;
}

class FreeList
{
public:
    void PushRange(void *start, void *end, size_t size) // 一次性插入一段空间
    {
        ObjNext(end) = _freelist;
        _freelist = start;

        _size += size; // 直接用size参数可以避免遍历start->end这份空间
    }
    void PopRange(void *&start, void *&end, size_t n /*要删除的块的数量*/) // 通过start和end获取n块空间
    {
        assert(n <= _size); // 此时的删除的块数不能超过当前freelist所管理的size块

        start = end = _freelist;

        for (int i = 0; i < n - 1; i++)
        {
            end = ObjNext(end); // end向后移动n-1步，这样start和end之间一共就有了n块空间
        }

        ObjNext(_freelist) = ObjNext(end); //_freelist这时候需要指向end后面的一块空间
        ObjNext(end) = nullptr;            // end的下一块指向nullptr
        _size -= n;                        // 这时候，该链表管理的块数-n
    }
    void Push(void *obj) // 用来回收空间
    {
        assert(obj); // 这里需要插入的是一个非空的空间
        // *(void**)obj =  _freelist; // *(void**)这种方式可读性不高，所以可以使用一个专门的接口来表示
        // 头插
        ObjNext(obj) = _freelist;
        _freelist = obj;
        _size++;
    }
    void *Pop() // 用来提供空间
    {
        assert(_freelist); // 要想提供空间那就一定要有空间
        // 头删
        void *obj = _freelist;
        _freelist = ObjNext(obj);
        _size--;

        return obj;
    }
    bool Empty()
    {
        return _freelist == nullptr;
    }
    size_t Size()
    {
        return _size;
    }

public:
    size_t &MaxSize()
    {
        return _max_size;
    }

private:
    void *_freelist = nullptr; // 自由链表，初始为空
    size_t _max_size = 1;      // 当前自由链表申请未达到上限的时候，能够申请的最大块空间是多少
                               // 初始值为1，表示当前最多能申请一块空间
                               // 达到上限后，这个_max_size就无效了
    size_t _size = 0;          // 表示当前链表一共管理的块数
};

struct Span
{
public:
    PageID _page_id = 0;  // 页号
    size_t _n = 0;        // 页的数量
    size_t _obj_size = 0; // span管理页被切分成的块的大小

    Span *_prev = nullptr; // 该节点的上一个节点
    Span *_next = nullptr; // 该节点的下一个节点

    void *_freelist = nullptr; // 该链表用于串起对应哈希桶所对应大小的空间块
    size_t _use_count = 0;     // 用于表示当前span分配出去的内存块的数量，初始值为0
                               // 当_usecount为0的时候可以把这部分空间向PageCache提交，用于合成更大的页，解决内存碎片化的问题（外碎片）
    bool _is_use = false;      // 判断当前的span是在CentralCache中还是PageCache中
                          // false表示当前的span没有被使用，说明还在PageCache中，true则说明这个span已经投入使用了，说明已经在CentralCache中了
};

class SpanList
{
public:
    SpanList()
    {
        _head = new Span;

        _head->_prev = _head;
        _head->_next = _head;
    }

public:
    bool Empty()
    {
        return _head->_next == _head; // 假如头尾相连说明此时spanlist上没有span
    }

public:
    void PushFront(Span *span)
    {
        Insert(Begin(), span);
    }
    Span *PopFront()
    {
        Span *front = _head->_next; // 获得头节点
        Erase(front);               // 从spanlist中将这个节点删除
        return front;
    }

public:
    void Insert(Span *pos, Span *ptr) // 在pos前插入ptr
    {
        // cout << "Insert Begin" << endl;
        assert(pos);
        assert(ptr);
        // assert(pos && ptr);

        auto prev = pos->_prev;

        ptr->_prev = prev;
        prev->_next = ptr;

        ptr->_next = pos;
        pos->_prev = ptr;

        // cout << "Insert End" << endl;
    }
    void Erase(Span *pos) // 删除pos位置的节点
    {
        assert(pos);
        assert(pos != _head);

        auto prev = pos->_prev;
        auto next = pos->_next;

        prev->_next = next;
        next->_prev = prev;
        // pos节点不需要删除，因为在内存池中，我们需要的是将这个空间回收
    }

public:
    Span *Begin() // 返回头节点
    {
        return _head->_next;
    }
    Span *End() // 返回尾节点
    {
        return _head;
    }

public:
    std::mutex _mtx; // 锁
private:
    Span *_head; // 哨兵位（头节点）
};

// Single-level array
template <int BITS>
class TCMalloc_PageMap1
{
private:
    static const int LENGTH = 1 << BITS; // 数组要开的长度
    void **array_;                       // 底层存放指针的数组

public:
    typedef uintptr_t Number;

    explicit TCMalloc_PageMap1()
    { // 开空间
        size_t size = sizeof(void *) << BITS;
        size_t align_size = SizeClass::_RoundUp(size, 1 << PAGE_SHIFT);
        array_ = (void **)SystemAlloc(align_size >> PAGE_SHIFT);
        memset(array_, 0, sizeof(void *) << BITS);
        cout << (sizeof(void*) << BITS) << endl;
    }

    // Return the current value for KEY.  Returns NULL if not yet set,
    // or if k is out of range.
    void *get(Number k) const
    { // 通过k来获取对应的指针
        if ((k >> BITS) > 0)
        {
            return NULL;
        }
        return array_[k];
    }

    // REQUIRES "k" is in range "[0,2^BITS-1]".
    // REQUIRES "k" has been ensured before.
    //
    // Sets the value 'v' for key 'k'.
    void set(Number k, void *v)
    { // 将v设置到k下标
        cout << "K: "<< k << endl;
        array_[k] = v;
    }
};